Lecture 6 - Practice

1. مفهوم Backtracking

الـ Backtracking يعني إن PROLOG لما يلاقي حاجة غلط بيرجع تاني يجرب حل تاني.

مثال:

likes(ahmed, football).
likes(ahmed, tennis).
likes(sara, tennis).

?- likes(ahmed, X).
X = football ;
X = tennis.

لما لقى أول حل (football) وقف. لو ضغطنا ; بيرجع يجرب تاني (backtracking).

ليه محتاج Cut؟

الـ Cut (!) بيوقف الـ Backtracking عشان نمنع جرب حلول زيادة أو نمنع جرب قواعد تانية.

2. قاعدة f(X, Y) بثلاث طرق

القاعدة الأساسية (من غير Cut)

f(X, 0) :- X < 3.
f(X, 2) :- X =:= 3.
f(X, 4) :- X > 3.

تحليل ?- f(1, Y), 2 < Y:

1. Rule 1: X=1, 1<3 true → Y=0
2. 2<0? false → backtrack
3. Rule 2: X=1, 1=:=3? false → backtrack
4. Rule 3: X=1, 1>3? false
5. Result: false

تحليل ?- f(5, Y), 2 < Y:

1. Rule 1: X=5, 5<3? false
2. Rule 2: X=5, 5=:=3? false
3. Rule 3: X=5, 5>3? true → Y=4
4. 2<4? true
5. Result: Y=4

Green Cut (Cut سليم)

f(X, 0) :- X < 3, !.
f(X, 2) :- X =:= 3, !.
f(X, 4) :- X > 3.

تحليل ?- f(1, Y), 2 < Y:

1. Rule 1: X=1, 1<3 true → ! → Y=0
2. 2<0? false → backtrack للـ Cut
3. Cut يمنع جرب القواعد التانية
4. Result: false

تحليل ?- f(5, Y), 2 < Y:

1. Rule 1: X=5, 5<3? false (قبل الـ Cut)
2. Rule 2: X=5, 5=:=3? false (قبل الـ Cut)
3. Rule 3: X=5, 5>3? true → Y=4
4. 2<4? true
5. Result: Y=4 (Green cut مش غيّر السلوك)

Red Cut (Cut خطر)

f(X, 0) :- !, X < 3.
f(X, 2) :- !, X =:= 3.
f(X, 4) :- X > 3.

تحليل ?- f(1, Y), 2 < Y:

1. Rule 1: ! يثبت الاختيار, X<3? true → Y=0
2. 2<0? false → backtrack للـ Cut
3. Cut يمنع جرب أي حاجة تانية
4. Result: false

تحليل ?- f(5, Y) (مشكلة!):

1. Rule 1: ! يثبت الاختيار, 5<3? false
2. Cut يمنع الرجوع للقواعد التانية
3. Result: false (مع إنه المفروض يطلع Y=4!)
4. الخلاصة: Red Cut غيّر السلوك المنطقي وخلّى الحل الصح يضيع.

3. إيجاد القيمة العظمى (Maximum)

من غير Cut

max(X, Y, X) :- X >= Y.
max(X, Y, Y) :- X < Y.

?- max(5, 3, M).
M = 5 ;
false.

بـ Green Cut

max(X, Y, X) :- X >= Y, !.
max(X, Y, Y).

?- max(5, 3, M).
M = 5.

?- max(3, 3, M).
M = 3.

الـ Cut هنا أمنع جرب القاعدة التانية لو الأولى نجحت.

4. دوال بشرط (Functions with Cut)

y = 3X       (X =< 5)
y = X^2 + 5  (X > 5)

func(X, Y) :- X =< 5, !, Y is 3 * X.
func(X, Y) :- X > 5, Y is X * X + 5.

?- func(3, Y).
Y = 9.

?- func(7, Y).
Y = 54.

بدون Cut:

% من غير Cut محتاج الشرط التاني صريح
func2(X, Y) :- X =< 5, Y is 3 * X.
func2(X, Y) :- X > 5, Y is X * X + 5.

5. تصنيف الأرقام (Classify Number)

classify(N) :-
    N > 0, !,
    write('Positive').

classify(N) :-
    N =:= 0, !,
    write('Zero').

classify(_) :-
    write('Negative').

?- classify(5).
Positive

?- classify(0).
Zero

?- classify(-3).
Negative

6. تقسيم القائمة (Split)

split بتفصل الأرقام الموجبة والسالبة في ليستتين.

split([], [], []).

split([H|T], [H|P], N) :-
    H >= 0, !,
    split(T, P, N).

split([H|T], P, [H|N]) :-
    split(T, P, N).

?- split([1, -2, 3, -4, 5], P, N).
P = [1, 3, 5], N = [-2, -4].

?- split([-1, -2, 0, 3, -4], P, N).
P = [0, 3], N = [-1, -2, -4].

7. تصنيف لاعب التنس (Tennis Player)

winner(rafa).
winner(federer).

fighter(rafa).
fighter(djoko).
fighter(nadal).

sportsman(rafa).
sportsman(federer).
sportsman(djoko).
sportsman(nadal).

tennis(X) :-
    winner(X), !,
    write('winner').

tennis(X) :-
    fighter(X), !,
    write('fighter').

tennis(X) :-
    sportsman(X), !,
    write('sportsman').

?- tennis(rafa).
winner

?- tennis(federer).
winner

?- tennis(djoko).
fighter

?- tennis(nadal).
fighter

?- tennis(sampras).
sportsman  % مش فاضل غير sportsman

8. عضو بدون تكرار (Single-Solution Membership - member1)

member1(X, [X|_]) :- !.

member1(X, [_|T]) :-
    member1(X, T).

الفرق بين member و member1:

% member بيرجع كل الحلول
?- member(a, [a, b, a, c]).
true ;
true ;     % تاني حل
false.

% member1 بيرجع أول حل بس وبعدين يقف
?- member1(a, [a, b, a, c]).
true.

9. إضافة بدون تكرار (Add Without Duplication)

add_no_dup(X, L, L) :-
    member1(X, L), !.

add_no_dup(X, L, [X|L]).

?- add_no_dup(3, [1, 2, 3], R).
R = [1, 2, 3].

?- add_no_dup(5, [1, 2, 3], R).
R = [5, 1, 2, 3].

10. توقع الناتج - أسئلة (Q7 Output Predictions)

س 1: إيه ناتج member(a, [b, a, c]).؟

true

(PROLOG يرجع true ويقف مستني)

س 2: إيه ناتج member1(a, [b, a, c]).؟

true

(member1 باستخدام cut بيوقف بعد أول حل)

س 3: إيه الفرق بين outputs بتوع member و member1 في [a, b, a, c]؟

• member: true ; true ; false
• member1: true

س 4: إيه ناتج add(1, [2, 3], R)؟

R = [1, 2, 3]

س 5: إيه ناتج add_no_dup(1, [2, 3, 1], R)؟

R = [2, 3, 1]

(لأن 1 موجود فعلاً)

س 6: إيه ناتج add_no_dup(4, [1, 2, 3], R)؟

R = [4, 1, 2, 3]

س 7: إيه ناتج ?- max(3, 5, M) من غير Cut؟

M = 5 ;
false.

(لأنه بعد M=5 يرجع يجرب القاعدة التانية عادي)